#pragma once
#include <vector>

using namespace std;

/* 元素交换 */
void swap(vector<int> &nums, int i, int j)
{
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

/* 选取三个候选元素的中位数 */
int medianThree(vector<int> &nums, int left, int mid, int right)
{
    // 此处使用异或运算来简化代码
    // 异或规则为 0 ^ 0 = 1 ^ 1 = 0, 0 ^ 1 = 1 ^ 0 = 1
    if ((nums[left] < nums[mid]) ^ (nums[left] < nums[right]))
        return left;
    else if ((nums[mid] < nums[left]) ^ (nums[mid] < nums[right]))
        return mid;
    else
        return right;
}

/* 哨兵划分（三数取中值） */
int partition(vector<int> &nums, int left, int right)
{
    // 以 nums[left] 为基准数
    // 选取三个候选元素的中位数
    int med = medianThree(nums, left, (left + right) / 2, right);
    // 将中位数交换至数组最左端
    swap(nums[left], nums[med]);

    int i = left, j = right;
    while (i < j)
    {
        while (i < j && nums[j] >= nums[left])
            j--; // 从右向左找首个小于基准数的元素

        while (i < j && nums[i] <= nums[left])
            i++;                // 从左向右找首个大于基准数的元素
        swap(nums[i], nums[j]); // 交换这两个元素
    }
    // now i==j,we exchange pivot
    swap(nums[i], nums[left]); // 将基准数交换至两子数组的分界线
    return i;                  // 返回基准数的索引
}

// void quickSort(vector<int> &nums, int left, int right)
// {
//     // 子数组长度为 1 时终止递归
//     if (left >= right)
//         return;
//     // 哨兵划分
//     int pivot = partition(nums, left, right);
//     // 递归左子数组、右子数组
//     quickSort(nums, left, pivot - 1);
//     quickSort(nums, pivot + 1, right);
// }

/* 快速排序（尾递归优化） */
void quickSort(vector<int> &nums, int left, int right)
{
    // 子数组长度为 1 时终止
    while (left < right)
    {
        // 哨兵划分操作
        int pivot = partition(nums, left, right);
        // 对两个子数组中较短的那个执行快速排序
        if (pivot - left < right - pivot)
        {
            quickSort(nums, left, pivot - 1); // 递归排序左子数组
            left = pivot + 1;                 // 剩余未排序区间为 [pivot + 1, right]
        }
        else
        {
            quickSort(nums, pivot + 1, right); // 递归排序右子数组
            right = pivot - 1;                 // 剩余未排序区间为 [left, pivot - 1]
        }
    }
}